/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class BoldWordsinString {
	public String boldWords(String[] words, String S) {
		// 消除多余的word
		int n = words.length;

		int m = S.length();
		HashMap<Integer, Integer> start2End = new HashMap<>();
		for (int i = 0; i < m; i++) {
			String sub = S.substring(i);
			int end = i;
			boolean find = false;
			for (String string : words) {
				if (sub.startsWith(string)) {
					find = true;
					end = Math.max(end, i + string.length());
				}
			}
			if (find) {
				// 查找是否有可以连接起来的
				boolean needPut = true;
				for (Integer p : start2End.keySet()) {
					int q = start2End.get(p);
					if (q >= i) {// 连接起来
						needPut = false;
						if (q < end) {
							start2End.put(p, end);
							break;
						}
					}
				}
				if (needPut)
					start2End.put(i, end);
			}
		}

		StringBuilder reStringBuilder = new StringBuilder();
		int i = 0;
		while (i < m) {
			if (start2End.containsKey(i)) {
				int end = start2End.get(i);
				reStringBuilder.append("<b>");
				reStringBuilder.append(S.substring(i, end));
				reStringBuilder.append("</b>");
				i = end;
			} else {
				reStringBuilder.append(S.charAt(i));
				i++;
			}
		}
		return reStringBuilder.toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] words = { "b", "dee", "a", "ee", "c" };
		String S = "cebcecceab";
		System.out.println(new BoldWordsinString().boldWords(words, S));
	}

}
